import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: MENG
 * Date: 2022-07-20
 * Time: 20:57
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
        this.usedSize = 0;
    }

    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        usedSize  = elem.length;
    }

    /**
     * 建堆:【大根堆】
     * 时间复杂度：O(n)
     */

    public void createHeap(){
        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--){
            shiftDown(parent,usedSize);
        }
    }

    //向下调整建立大根堆
    public void shiftDown(int parent, int len){
        int child = parent * 2 + 1;
        //有左孩子
        while(child < len){
            //有右孩子并且，左孩子小于右孩子
            if(child + 1 < len && elem[child] < elem[child+1]){
                child++;
            }
            if(elem[child] > elem[parent] ){
                swap(elem,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    //交换两个值
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * 入队
     * @param x
     */
    public void offer(int x){
        //如果现在数组满了，那就2倍扩容一下。
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //在usedSize下标处（这里是10）插入元素x
        this.elem[usedSize] = x;
        usedSize++;
        //调用向上调整的方法，把插入元素的下标传进去，这里是usedSize-1下标
        shiftUp(usedSize-1);

    }

    private void shiftUp(int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }

    }

    public boolean isFull(){
        return usedSize == elem.length;
    }

    /**
     * 出队
     */
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int old = elem[0];//记录一下要删除的堆顶元素
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

    //堆排序
    public void heapSort(){
        int end = usedSize -1;
        while(end > 0){
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }

    }
}
